package com.heima.leetcode.datastructure.binarysearchtree;

/**
 * <strong>离两个节点最近的公共祖先 235</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/13 16:06
 */
public class LowestCommonAncestor {
    // p、q最近的公共祖先就是从上到下第一次出现分叉的节点
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode curr = root;
        while (curr != null){
            if (p.val < curr.val && q.val < curr.val){
                curr = curr.left;
            }else if (p.val > curr.val && q.val > curr.val){
                curr = curr.right;
            }else {
                return curr;
            }
        }
        return null;
    }
}
